class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> submit = new ArrayList<>();
    
    public List<List<Integer>> subsets(int[] nums) {
        dfs(0,nums);
        return res;
    }
    private void dfs(int cur,int[] nums) {
        if(cur == nums.length) {
            res.add(new ArrayList<Integer>(submit));
            return;
        }
        //选择加入nums[cur]
        submit.add(nums[cur]);
        dfs(cur+1,nums);
        submit.remove(submit.size()-1);
        //选择不加入nums[cur]
        dfs(cur+1,nums);

    }


    public List<List<Integer>> subsets1(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>(); // 解集
        lists.add(new ArrayList<Integer>()); // 首先将空集加入解集中
        for(int i = 0; i < nums.length; i++){
            int size = lists.size(); // 当前子集数
            for(int j = 0; j < size; j++){ 
                List<Integer> newList = new ArrayList<>(lists.get(j));// 拷贝所有子集
                newList.add(nums[i]); // 向拷贝的子集中加入当前数形成新的子集
                lists.add(newList); // 向lists中加入新子集
            }
        }
        return lists;
    }
}